package leetcode_git;

import java.util.Scanner;

/**
 * @author huangxiaoming
 * @date 2022/5/30
 **/
public class Test4 {

    /**
     * 题目描述：有 N 个 信 和 信封，它们被打乱，求错误装信方式的数量。
     * <p>
     * 定义一个数组 dp 存储错误方式数量，dp[i] 表示前 i 个信和信封的错误方式数量。假设第 i 个信装到第 j 个信封里面，而第 j 个信装到第 k 个信封里面。根据 i 和 k 是否相等，有两种情况：
     * <p>
     * i==k，交换 i 和 j 的信后，它们的信和信封在正确的位置，但是其余 i-2 封信有 dp[i-2] 种错误装信的方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-2] 种错误装信方式。
     * i != k，交换 i 和 j 的信后，第 i 个信和信封在正确的位置，其余 i-1 封信有 dp[i-1] 种错误装信方式。由于 j 有 i-1 种取值，因此共有 (i-1)*dp[i-1] 种错误装信方式。
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            System.out.println(rob(n));
        }
    }

    private static int rob(int n) {
        if(n == 0 || n == 1) return 0;
        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2; i < n; ++i){
            dp[i] = (i - 1) * (dp[i-2] + dp[i-1]);
        }
        return dp[n - 1];
    }
}
